This application claims priority to an application entitled xe2x80x9cApparatus and Method for Selecting Optimal Satellites in Global Positioning Systemxe2x80x9d filed in the Korean Industrial Property Office on Jun. 12, 2002 and assigned Serial No. 2002-32955, the contents of which are hereby incorporated by reference.
1. Field of the Invention
The present invention relates generally to GPS (Global Positioning System), and in particular, to an apparatus and method for selecting optimal GPS satellites to locate an object.
2. Description of the Related Art
Along with today""s dramatic development in personal, portable communication devices, a variety of additional services are supported. In particular, some countries have mandated the use of positioning devices such as GPS in mobile terminals to provide location-based services to users.
Many GPS satellites broadcast their ephemeredes and system time, circling the earth in predetermined orbits, so that GPS receivers can determine their positions. The orbits of GPS satellites are carefully chosen so that at least four of them can be observed around the earth to allow the locations, velocities, and clock errors of the GPS receivers to be calculated. The GPS receivers can trace their positions with an error of 20 or less meters in urban areas.
Navigation data broadcasted from each satellite contains the PRN (Pseudo-Random Noise) code of the satellite corresponding to its satellite ID. Since the GPS navigation message is transmitted in CDMA (Code Division Multiple Access) format, a GPS receiver can receive the navigation data from each satellite accurately. The GPS receiver calculates its position using the navigation data. With the use of its internal algorithm, the GPS receiver tracks GPS satellite signals. Once it tracks one satellite signal, the GPS receiver can achieve information about the relative positions of other satellites using the received satellite orbit infomation. Thus the GPS receiver can track signals from all available satellites within a short period of time. Recently, the A-GPS (Assisted-GPS) is widely used which enables a GPS receiver to receive the ephemeris and timing information from a base station. Therefore, information of all available satellites is immediately available to the GPS receiver.
In general, a GPS receiver on the ground can observe 6 to 12 satellites simultaneously. To initially acquire CDMA signals from the satellites, a typical GPS receiver is required to search a wide range of frequency and code for each satellite signal. This search process is a major time-consuming factor that determines time to first fix (TTFF).
The GPS receiver can acquire at least 4 satellite signals more rapidly by assigning a plurality of independent channels to track the satellite signals. However, a system such as a small-sized portable terminal having a limited size uses a relatively small number of hardware channels and, in some cases, assigns multiple hardware channels to one satellite to reduce the TTFF.
In this case, it is difficult to track all the satellites that are visible to the GPS receiver because of the limited number of hardware channels. Thus, the GPS receiver selectively tracks a subset of visible satellites. The accuracy of a navigational solution, when a fixed number of satellites is to be selected, depends mainly on the quality of the subset (GDOP) that is being selected. Accordingly, a number of methods of selecting satellites that minimizes the positioning error of the GPS receiver (hereinafter, referred to as optimal satellites) have been proposed.
The primary requirements for optimal satellites are that they must minimize GDOP (Geometric Dilution Of Precision) and that their signals can actually be acquired through tracking. If GDOP is not minimized, position error could increase by a factor of five or more in some cases.
A unit vector pointing from a GPS receiver to a satellite i is defined as an LOS (Line-Of-Sight) vector losi. If there are N visible satellites in the three-dimensional space, their coordinates can be expressed as an Nxc3x973 (x, y, z coordinates)-LOS matrix of                     H        =                              [                                                                                x                    1                                                                                        y                    1                                                                                        z                    1                                                                                                                    x                    2                                                                                        y                    2                                                                                        z                    2                                                                                                                    xe2x80x83                                                                    …                                                                      xe2x80x83                                                                                                                    x                    N                                                                                        y                    N                                                                                        z                    N                                                                        ]                    =                      [                                                                                los                    1                                                                                                                    los                    2                                                                                                …                                                                                                  los                    N                                                                        ]                                              (        1        )            
where H represents line of sight matrix for N visible satellites.
When n satellites are to be selected from N number of the total visible satellites, NCn number of satellite combinations can be produced where NCn represents the number of combinations of the n selected satellites among the N visible satellites. Then, T (T=NCn) number of nxc3x973 LOS matrices h1, h2, . . . , hT are formed. The selected line of sight (LOS) matrices are represented by h. Using the jth combination hj, the position of the GPS receiver is calculated by using the following linearized equation
xcex4{overscore ("PHgr")}=hjxcex4{overscore (x)}+{overscore (xcexd)}xe2x80x83xe2x80x83(2)
where xcex4{overscore ("PHgr")} is an (nxc3x971) vector containing measurements received from satellites, xcex4{overscore (x)} is a three-dimensional vector with which an intended navigational solution is updated, and {overscore (xcexd)} is an (nxc3x971) vector indicating the measurement noise of the satellite signals (Ev=0 and EvvT="sgr"2I. Here, "sgr" is the noise standard deviation and I is an identity matrix).
The estimation procedure of the xcex4{overscore (x)} is
xcex4{overscore (x)}=(hjThj)xe2x88x921hjTxcex4{overscore ("PHgr")}xe2x88x92(hjThj)xe2x88x921hjT{overscore (xcexd)}
xcex4{overscore (x)}=(hjThj)xe2x88x921hjTxcex4{overscore ("PHgr")}xe2x80x83xe2x80x83(3)
The influence of the measurement error {overscore (xcexd)} on the navigational solution is calculated by
xcexde=(hjThj)xe2x88x921hjT{overscore (xcexd)}xe2x80x83xe2x80x83(4)
The statistics of the effective noise xcexde is
Excexde=E[(hjThj)xe2x88x921hjT{overscore (xcexd)}]=0
ExcexdexcexdeT=E[(hjThj)xe2x88x921hjT{overscore (xcexd)}xcexdThj
(hjThj)xe2x88x921]=(hjThj)xe2x88x921"sgr"2xe2x80x83xe2x80x83(5)
From Eq. (5) GDOP is defined as
GDOP={square root over (TRACE [(hjThj)xe2x88x921])}xe2x80x83xe2x80x83(6)
Where TRACE is an operator that indicates the sum of the diagonal elements of the matrix, which is equal to the sum of all Eigen-values. It is noted from Eq. (6) that the measurement error of the GPS receiver is influenced by the geometrical positions hj of satellites. If GDOP is less than 1, the effective noise standard deviation is less than the measurement noise standard deviation. If GDOP is larger than 1, the former is higher than the latter by a multiple of GDOP. Therefore, it is desired to select the combination h that minimizes GDOP in order to achieve an optimal navigational solution.
FIG. 1 is a flowchart illustrating a conventional satellite selection method for optimal satellite selection. In the optimal satellite selection, GDOP is calculated for all possible subsets of the available satellites and the subset that minimizes the GDOP is selected by comparing the GDOPs of all possible subsets. It is assumed in this process that a GPS receiver has already received information about the relative positions of all the other satellites from an initially observed satellite.
Referring to FIG. 1, the GPS receiver calculates N unit vectors (LOS vectors) representing the three-dimensional coordinates of N available/visible satellites with respect to the GPS receiver, using the relative positions of the satellites in step S10 and generates T (=NCn) LOS combinations h1, h2, . . . , hT from the N LOS vectors in step S20. The GPS receiver sets a variable k to 1 in step S30. The variable k is used to identify a LOS combination. The GPS receiver calculates the GDOP for a kth combination, GDOP(k) by TRACE(hkThk)xe2x88x921 in step S40 and stores it in step S50. After calculating the GDOPs for all T number of combinations, increasing the variable by 1 at each time in step S60 until the variable k is T in step S70, the GPS receiver compares the GDOPs and chooses the LOS combination that has the minimum GDOP in step S80. Then the GPS receiver assigns channels to the PRN codes of the satellites included in the chosen LOS combination.
The GDOP calculation and storage for all the LOS combinations requires a very large number of operations including matrix inversions. FIG. 2 is a listing of numbers of matrix combinations required for the optimal satellite selection. Referring to FIG. 2, the number of matrix combinations grows by geometric progression as the number N of visible satellites and the number n of satellites to be chosen increase. Therefore, despite its effectiveness in selecting optimal satellites, the optimal satellite selection has the shortcomings of the long operation time, impossible real time operation, requirement for a large number of operation circuits, large-capacity memory requirement, great power consumption, limited integration, and the resulting limitations in application for small portable systems. Moreover, if the Galileo system, similar to GPS, already under development under ESA (European Space Agency) were to be deployed, more satellites could be observed. In such case, the number of subsets of satellites and the required operation volume would further increase.
Another conventional satellite selecting method is a highest elevation satellite selection method. In principle, this method selects the subset of satellites with the highest elevations with respect to a user. The algorithm requires very little computation. However, since satellites in only one direction may be selected, minimization of GDOP cannot be guaranteed. In real application, a GDOP achieved in this scheme is larger than a GDOP achieved in the optimal satellite selection by about 2 to 10 times, which implies that the error of a navigational solution is 2 to 10 times higher. When a GPS receiver is indoors or in an area crowded with buildings, the receiver may fail to acquire signals if it attempts to track satellites in one direction only.
It is, therefore, an object of the present invention to provide an apparatus and method for selecting GPS satellites to locate an object.
It is another object of the present invention to provide an apparatus and method for selecting GPS satellites without directional redundancy.
It is a further object of the present invention to provide an apparatus and method for selecting optimal satellites using minimum operation.
It is still another object of the present invention to provide an apparatus and method for selecting optimal satellites, suitable for small portable systems.
To achieve the above and other objects, there is provided an apparatus and method for selecting optimal GPS satellites to locate an object.
According to an aspect of the present invention, to select optimal satellites, a satellite list including the coordinates of satellites is made, the redundancies of the satellites are calculated, at least one satellite having a maximum redundancy is eliminated from the satellite list, and channels of a GPS receiver are assigned to an intended number of satellites if the intended number of satellites remain in the satellite list.
According to another aspect of the present invention, to select optimal satellites, a satellite list including the coordinates of effective satellites is made, the redundancies of the satellites are calculated, the satellite list is updated by eliminating at least one satellite having a maximum redundancy from the satellite list, the redundancy calculation and the satellite list updating are repeated for the updated satellite list until an intended number of satellites remain in the updated satellite list, and channels of a GPS receiver are assigned to the intended number of satellites if the intended number of satellites remain in the satellite list.
According to a further aspect of the present invention, in a satellite electing apparatus, an RF unit receives RF signals on channels assigned to GPS satellites, a digital unit processes the received RF signals, a processor unit selects satellites to which the channels are assigned and calculates a navigational solution using the processed signals, and a memory stores an operating program executed in the processor unit. Specifically, the processor unit makes a satellite list including the coordinates of satellites, calculates the redundancies of the satellites, eliminates at least one satellite having a maximum redundancy from the satellite list, and assigns the channels to an intended number of satellites if the intended number of satellites remain in the satellite list.
According to still another aspect of the present invention, in a satellite selecting apparatus, an RF unit receives RF signals on channels assigned to GPS satellites, a digital unit processes the received RF signals, a processor unit selects satellites to which the channels are assigned and calculates a navigational solution using the processed signals, and a memory stores an operating program executed in the processor unit. Specifically, the processor unit makes a satellite list including the coordinates of effective satellites, calculates the redundancies of the satellites included in the satellite list, updates the satellites list by eliminating at least one satellite having a maximum redundancy from the satellite list, calculates the redundancies of the satellites included in the updated satellite list, eliminates one satellite having a maximum redundancy from the updated satellite list, and assigns channels of a GPS receiver to an intended number of satellites if the intended number of satellites remain in the satellite list.